package leetcode.Fiftyone_to_One_hundred;

/**
 * 二进制求和
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 *
 * 输入为非空字符串且只包含数字 1 和 0。
 */
public class Test67 {

    public static String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            // 累加两个二进制数
            if (j >= 0)
                sum += b.charAt(j--) - '0';
            if (i >= 0)
                sum += a.charAt(i--) - '0';
            // 得到余数
            sb.append(sum % 2);
            // 拿到进位
            carry = sum / 2;
        }
        // 最后发现进位不等于 0 则需要添加进位
        if (carry != 0)
            sb.append(carry);
        // 结果需要逆序
        return sb.reverse().toString();
    }

//    public static String addBinary2(String a, String b) {
//        Integer m = Integer.parseInt(a, 2);
//        Integer n = Integer.parseInt(b,2);
//        return Integer.toBinaryString(m+n);
//    }

    public static void main(String[] args) {
        System.out.println(addBinary("1111", "11"));
    }
}
